#include <vector>

using namespace std;

class Solution {
public:
    int numSquares(int n) {
        if (n <= 3) {
            return n;
        }
        vector<int> num(n + 1, 0);
        num[0] = 0;
        num[1] = 1;
        num[2] = 2;
        num[3] = 3;
        for (int i = 4; i <= n; i++) {
            int number = 1;
            int square = 1;
            while (square <= i) {
                if (num[i] == 0) {
                    num[i] = num[square] + num[i - square];
                } else {
                    if (square == i) {
                        num[i] = min(num[i], 1);
                    } else {
                        num[i] = min(num[i], num[square] + num[i - square]);
                    }
                }
                number++;
                square = number * number;
            }
        }
        return num.back();
    }
};